1. Field of the Invention
Methods consistent with the present invention relate to broadcast encryption, and more specifically, to managing a user key for a broadcast encryption.
2. Description of the Related Art
Broadcast encryption (BE) is used for a sender (that is, a broadcast center) to efficiently transmit information to only intended users among all users. This scheme should be effectively used when a set of users receiving the information changes randomly and dynamically. In BE, the most important issue is to revoke or exclude disapproved users (for example, revoked users or expired users).
FIG. 1 is a conceptual view showing a network construction of a data transmission system in which a general broadcast encryption scheme is used. Referring to FIG. 1, a contents producer 100 produces various kinds of available contents of data, including audio or video data, and provides a service provider 110 with the produced contents of data. The service provider 110 broadcasts the contents of data provided from the contents producer 100 to privileged users (for example, a mobile Digital Right Management (DRM) network 140 and a smart home DRM network 150) who paid for corresponding contents of data provided through various kinds of wired or wireless communication networks.
That is, the service provider 110 can transmit the data to a user apparatus such as a set-top box 141 equipped with various kinds of satellite receivers via a satellite 120 and also to a mobile communication terminal 142 through a mobile communication network. Further, the provider 110 can transmit the data to various kinds of terminals 150, 151, 152, 153, 154 and 155 in the smart home DRM network 150 through an Internet network 130.
Meanwhile, at this time, in order to keep revoked users 160 who have not paid for using the data, the data is encrypted by using the broadcast encryption scheme.
Security in such an encryption/decryption system generally depends on an encryption key management scheme. Further, in such an encryption key management scheme, the most important matter is how to derive the encryption key. At the same time, it is also important to manage and update the derived encryption keys.
There have been many changes in BE since the concept was first proposed in 1991, and it is assumed that users are stateless in current BE schemes. This means that secret keys of each user are never changed or updated even though sessions change. By the way, the term “k-resilient” is used for security, which means that the revoked users cannot recover the data although k revoked users among all the revoked users collude. If r is the number of the revoked users, the term “r-resilient” means that there is no problem in security although all of the revoked users collude.
Meanwhile, another main issue of BE is to minimize transmission overhead, storage overhead and computation overhead, which means the length of headers to be transmitted by a sender, the size of user keys and the computing time of computations for a user to obtain a session key, respectively. Among them, in particular, the most important issue is to reduce the transmission overhead. While the transmission overhead was proportional to N which is the number of total users, these days it is generally and currently proportional to the number of the revoked users r. Accordingly the transmission overhead is reduced as r decreases. As schemes in which the transmission overhead is proportional to r have been developed, it became an important issue to reduce the transmission overhead down to less than r.
Among the published BE schemes, it is known that a Subset Difference (SD) method (or model) by D. Naor, M. Naor and J. Lotspiech shows the best efficiency. In the SD method, storage overhead is O(log3/2 n) and transmission overhead is O(2r−1) when the number of total users is n.
However, the SD method also is disadvantageous in efficiency when there are a number of users.
As described above, various algorithms have been proposed since 1991. Among them, a secret sharing scheme, a subset cover-free system model scheme and a tree-structure based scheme are important ones.
First, a secret key sharing model will be schematically described below. The secret key sharing model was proposed by S. Berkovits in 1991, and improvement thereof is made in a paper entitled “Efficient Trace and Revoke Schemes” published by M. Noar and B. Pinkas in 2000. A polynomial interpolation method and a vector-based secret key sharing method were proposed in a paper entitled “How to Broadcast a Secret” by S. Berkovits.
In the polynomial interpolation method, a center (that is, a broadcast center or a sender) transmits a point (xi, yi) to each user over a secret channel. At this time, all of the Xi are different from each other and the point (xi, yi) is a secret key of each user. Then, in order for a center to broadcast secret information S to t privileged users by a session, t+j+1 degree of a polynomial P and a random integer j are selected. The polynomial P is a polynomial expression on the points (xi, yi) which are the secret keys of privileged users, randomly selected j points (x, y) that are not secret keys of any other privileged users and a point (O, S). Further, the center transmits any points which are on the polynomial P but not included in the (t+j) points. Then, since the t privileged users know one more point (their own secret key) other than the (t+j) points, they can obtain the t+j+1 degree of polynomial P and also decrypt the secret information S. However, the revoked users know only (t+j) points, so that they can not obtain the polynomial P.
This method has transmission overhead of O(t+j+1), storage overhead of O(1), and computation overhead of t3 times of computations, approximately. Therefore, the method has advantages that it is easy to revoke unprivileged users and keep the revoked users from colluding, and further traitor tracing is possible. However, this method has also a disadvantage that it cannot be practically used since it is not efficient for a large group of users and security becomes weaker after the method is repeatedly used many times. A threshold secret sharing scheme using the Lagrange's interpolation formula is used in schemes proposed in a paper entitled “Efficient Trace and Revoke Schemes” by M. Noar and B. Pinkas. The schemes proposed by Noar-Pinkas use an idea that a polygonal expression of (r+1) degree can be recovered using (r+1) points on the polynomial of (r+1) degree but cannot be recovered with r points that lack one point to recover the polynomial of (r+1) degree. That is, the center selects arbitrary polynomial P of t degree and gives each user with each different point on the polynomial P as a secret key. When r users are revoked, the center transmits t total points, that is, r secret keys, which are r revoked users' keys, and (t−r) points selected arbitrarily to the revoked users. As a result, since revoked users know only t points, including his/her secret key, the revoked users can not recover the polynomial P. Meanwhile, since a user who is not revoked knows (t+1) points, the user can recover the polynomial P. By this polynomial P, a session key P(0) is obtained.
This method has advantages that revocation is also easy and it is possible to keep revoked users from colluding. Further, it has remarkable advantages that it is possible to add new users and has a quite good efficiency of the transmission overhead O(t) and the storage overhead O(1). However, this method also has a problem that it is impossible to revoke more users than t which is the initially determined number. Furthermore, this method is sometimes inefficient in many cases, since the number of points to be transmitted and the computation overhead to compute a polynomial depend on the t. Still further, since the computing time dramatically increases as t becomes greater, this scheme is not proper in a case that there are a number of users.
Secondly, a subset cover-free system model can be applied when a set of total users S comprises a plurality of subsets. BE can be performed by using the subset cover-free system. However, the system is not efficient because the storage overhead and transmission overhead become about O(r log n). Further, a k-resilient model is proposed by expanding a 1-resilient model. Since effective 1-resilient technique can be easily devised such expansion seems to be meaningful, but efficiency is quite degraded during the expansion procedure using the methods known until now.
Thirdly, tree-structure based methods are recently attracting public attention. Although C. K. Wong, M. Gouda and G. S. Lam proposed a logical-tree-hierarchy (LTH) method in 1998, it was hard to revoke a number of users in one session. Further, since user secret keys change as the sessions change in this method, it is not applicable to up-to-data BE which assumes that receivers are stateless. Later, D. Naor, M. Noar and J. Lotspiech proposed a Complete Subset (CS) Cover scheme and the SD scheme in 2001. In both methods, given that n is the number of total users and r is the number of revoked users, a center constructs a binary tree with the height (log n) and assigns secret keys to each node in the binary tree. Further, each node is assigned each user.
First, considering a CS Cover Scheme, each user receives all secret keys of the nodes located on its path starting from the root node to its own leaf from a center, and stores them. Here, a sub-tree including no revoked user is called a CS. At this time, it is possible to form a tree structure that does not include any revoked users, by gathering the CSs properly. When a center encrypts each session key by using each secret key of the root nodes of the CSs and transmits the encrypted session keys to corresponding CSs, privileged users can recover the session keys but the revoked users cannot recover the session keys since they are not included in any of the CSs.
FIG. 2 is a tree structure showing a concept of a broadcast encryption in which key distribution method follows the related art of the tree-structure based model. Referring to FIG. 2, a set of users 220 arranged onto corresponding nodes 32 to 47, respectively, receives data encrypted by using a broadcast encryption scheme. The users on their nodes 32 to 47 have their unique keys, respectively, along with keys of all of the nodes linked with their nodes, respectively in the tree-structure.
For example, the user on the node 34 has keys of the node 17, the node 8, the node 4 and the node 2 as well as his/her own key. That is, the key of the node 17, which is given to the user on the node 34, is shared with the user on the node 35. In the same manner, the key of the node 8, which is also given to the user on the node 34, is shared with the users on the nodes 32, 33, 35.
Meanwhile, in a case that all of the users on the nodes 32 to 47 are privileged, data transmission can be performed maintaining the data secrecy by transmitting the same data with a header which contains the key of the node 2 to all of the users.
However, if a user having the key originally assigned to the user 221 on the node 36 is a revoked user, since the key of the user 221 is shared with other users all of the keys in relation with the key of the user 221 should be updated. That is, the keys of the node 18, the node 9, the node 4 and the node 2 should be updated. At this time, the update of the keys is progressed upward from the lowest level nodes to the highest level nodes.
First, since the key of the node 18 corresponding to the user 210 is shared with the user on the node 37, the updated key of the node 18 corresponding to the user 210 is encrypted and transmitted to the user of the node 37 by the center. The key of the node 9 corresponding to the user 205 is shared with the user on the node 37, the users of the nodes 38 and 39 located in the lower level of the node 19 corresponding to the user 211. Accordingly, when applying the updated key of the user 205 on the node 9 to the nodes 37, 38 and 39 in a lower level, the previously updated key of the user 210 on the node 18 will be encrypted and transmitted to the user on the node 37. Meanwhile, the updated key of the node 19 will be encrypted and transmitted to the users on the nodes 38 and 39.
In the same manner, since the key of the node 4 corresponding to the user 202 is shared with the users on the nodes 32 to 35, which are downstream nodes of the node 8 corresponding to the user 204, and the users on the nodes 37 to 39 which are downstream nodes of the node 9 corresponding to the user 205, to apply the previously updated key of the node 4 corresponding to the user 202 to the nodes 32 to 35, the updated key of the node 8 corresponding to the user 204 is encrypted and transmitted to the nodes 32 to 35. Meanwhile, the updated key of the node 9 corresponding to the user 205 is encrypted and transmitted to the nodes 37 to 39.
Finally, since the key of the node 2 corresponding to the user 201 is shared with the users on the nodes 32 to 35 and 37 to 39, which are downstream nodes of the node 4 corresponding to the user 202, and the users on the nodes 42 to 47 which are downstream nodes of the node 5 corresponding to the user 203, to apply the previously updated key of the node 2 corresponding to the user 201 to the nodes 32 to 35, 37 to 39 and 42 to 47, the updated key of the node 4 corresponding to the user 202 is encrypted and transmitted to the nodes 32 to 35 and 37 to 39. Meanwhile, the updated key of the node 5 corresponding to the user 203 is encrypted and transmitted to the nodes 40 to 47. By this key update procedure, it is possible to keep the revoked user (or the expired user) from accessing the broadcasted data.
The transmission overhead in this CS model is the number of the all of CSs, O(r log(n/r)), in which the CSs do not include any revoked users. Further, the storage overhead is O(log n).
Meanwhile, the SD model is a modification of the CS model described above, and has remarkably improved the transmission overhead. That is, the transmission overhead is O(2r−1) and the storage size is O (log2n) in the SD method. In the SD model, it is assumed that there is a first sub-tree rooted at a node v. The sub-tree has a node w which also serves as the root of a second sub-tree. At this time, we can consider a third sub-tree including set of all leaves in the first sub-tree rooted at the node v but not including leaves in the second sub-tree rooted at the node w. All leaves in the third sub-tree are regarded as privileged users and all leaves in the second sub-tree are regarded as revoked users. In a case that there is a set of users including the reasonable number of privileged users and a small number of revoked users, only one-sub set is needed for this SD method unlike the CS method in which at least two sub-sets are needed. In the SD method, a hash value of keys assigned the nodes hanging off the path between the node v to the node w are obtained is obtained and the obtained hash value is used as a session key. That is, each node has a hash value of a sibling node of each node hanging off the path between the root node and his/her own node as a secret key. Accordingly, only privileged users can recover the session key due to the uni-directional property of the hash function. At this time, the transmission overhead of the SD model is 0(2r−1) at most, and the storage overhead of is 0(log2n), and the computation overhead of it is maximum 0(log n).
Thereafter, an LSD model improved from the SD model was proposed in 2002. In the LSD model, the storage overhead is reduced to 0(log3/2n) by applying a layer-structure to each sub-tree, but the transmission overhead becomes twice as much as that of the SD model.
The models with the best efficiency among the BE models described above are the tree-structure based modes, such as LSD, SD and the like. However, since the number of subsets needed for the broadcast in the method based on the tree-structure considerably depends on positions of the users further remarkable improvement is not expected. Further, the tree-structure based BE models have a drawback that they requires considerable amount of maintenance cost. Accordingly, more efficient BE models other than the tree-structure based models described above are demanded.